package it.unibo.refolding.common;

import it.unimi.dsi.fastutil.doubles.Double2IntAVLTreeMap;
import it.unimi.dsi.fastutil.doubles.Double2IntMap;
import it.unimi.dsi.fastutil.doubles.Double2IntSortedMap;
import it.unimi.dsi.fastutil.doubles.DoubleArrayList;
import it.unimi.dsi.fastutil.doubles.DoubleList;
import it.unimi.dsi.fastutil.floats.FloatArrayList;
import it.unimi.dsi.fastutil.ints.IntArrayList;
import it.unimi.dsi.fastutil.ints.IntCollection;
import it.unimi.dsi.fastutil.ints.IntList;
import it.unimi.dsi.fastutil.ints.IntListIterator;
import it.unimi.dsi.fastutil.objects.ObjectSortedSet;
import it.unimi.dsi.fastutil.shorts.ShortList;
import it.unimi.dsi.fastutil.shorts.ShortListIterator;

import java.awt.Shape;
import java.awt.geom.Rectangle2D;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.OutputStream;
import java.io.Serializable;
import java.io.UnsupportedEncodingException;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.nio.file.DirectoryStream;
import java.nio.file.DirectoryStream.Filter;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.PathMatcher;
import java.nio.file.Paths;
import java.nio.file.StandardOpenOption;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Locale;
import java.util.Map;
import java.util.Random;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.concurrent.Executor;
import java.util.logging.Level;
import java.util.logging.Logger;
import java.util.regex.Pattern;

import org.apache.commons.io.IOUtils;
import org.apache.commons.lang3.SerializationUtils;
import org.apache.commons.lang3.StringUtils;
import org.apache.commons.lang3.exception.ExceptionUtils;
import org.apache.commons.math3.stat.StatUtils;

import com.google.common.base.Objects;
import com.google.common.base.Preconditions;
import com.google.common.base.Predicate;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.collect.Range;

public class CommonThings {

  public static String FP_REGEX = "[-+]?\\d*\\.?\\d+(?:[eE][-+]?\\d+)?";
  public static String I_REGEX = "[-+]?\\d+";
  /*
   * Embedded flags always take effect at the point at which they appear,
   * whether they are at the top level or within a group; in the latter case,
   * flags are restored at the end of the group just as in Perl.
   */
  public static String B_REGEX = "(?i)(?:true)|(?:false)";

  private static final Logger logger = Logger.getLogger(CommonThings.class.getName());

  public static Pattern fpPattern = Pattern.compile("^" + FP_REGEX + "$");

  public static Runnable noopRunnable = new Runnable() {
    @Override
    public void run() {
    }
  };

  public static boolean parseBoolean(String s) {
    String a = s.toLowerCase(Locale.ROOT);
    switch (a) {
    case "true":
      return Boolean.TRUE;
    case "false":
      return Boolean.FALSE;
    default:
      throw new IllegalArgumentException("Only true and false are valid values, case-insensitive.");
    }
  }
  
  public static double mean(double[] x) {
    return mean(x, 0, x.length);
  }

  public static double mean(double[] x, int from, int to) {
    double xAvg = 0;
    int len = to - from;
    for (int i = from; i < to; ++i) {
      xAvg += x[i] / len;
    }
    return xAvg;
  }

  public static void serializeToFile(Serializable result, String filename) {
    try (OutputStream fos = Files.newOutputStream(Paths.get(filename))) {
      SerializationUtils.serialize(result, fos);
    } catch (IOException e) {
      throw new MyRuntimeException("Could not serialize result: " + e.getMessage(), e);
    }
  }

  @SuppressWarnings("unchecked")
  public static <T> T deserializeFromFile(String filename) {
    FileInputStream fis;
    try {
      fis = new FileInputStream(filename);
    } catch (FileNotFoundException e) {
      throw new MyRuntimeException("Could not open file: " + e.getMessage(), e);
    }
    Object o = SerializationUtils.deserialize(fis);
    return (T) o;
  }

  public static short[][] toNestedShortArray(short[] src) {
    int n = (int) Math.sqrt(src.length);
    Preconditions.checkArgument(src.length == n * n);
    short[][] dst = new short[n][];
    for (int i = n; --i >= 0;) {
      dst[i] = new short[n];
      for (int j = n; --j >= 0;) {
        short a = src[i * n + j];
        dst[i][j] = a;
      }
    }
    return dst;
  }

  public static boolean[][] toNestedBooleanArray(byte[] b) {
    int n = (int) Math.sqrt(b.length);
    Preconditions.checkArgument(b.length == n * n);
    boolean[][] a = new boolean[n][];
    for (int i = n; --i >= 0;) {
      a[i] = new boolean[n];
      for (int j = n; --j >= 0;) {
        a[i][j] = b[i * n + j] != 0;
      }
    }
    return a;
  }

  public static double euclideanDistance(IntPair a, IntPair b) {
    return Math.sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
  }

  public static <T> T last(T[] a) {
    return a[a.length - 1];
  }

  public static <T> T last(List<? extends T> a) {
    return a.get(a.size() - 1);
  }

  public static <T> T setLast(List<T> a, T b) {
    return a.set(a.size() - 1, b);
  }

  public static int argMin(double[] d) {
    return argMin(d, 0, d.length);
  }

  public static int argMin(double[] d, int from, int to) {
    Preconditions.checkArgument(from <= to);
    if (from == to) {
      return -1;
    }
    int i = from;
    for (int j = from + 1; j < to; ++j) {
      if (d[j] < d[i]) {
        i = j;
      }
    }
    return i;
  }

  public static int argMax(double[] d, int from, int to) {
    Preconditions.checkArgument(from <= to);
    if (from == to) {
      return -1;
    }
    int i = from;
    for (int j = from + 1; j < to; ++j) {
      if (d[j] > d[i]) {
        i = j;
      }
    }
    return i;
  }

  public static int argMax(short[] d, int from, int to) {
    Preconditions.checkArgument(from <= to);
    if (from == to) {
      return -1;
    }
    int i = from;
    for (int j = from + 1; j < to; ++j) {
      if (d[j] > d[i]) {
        i = j;
      }
    }
    return i;
  }

  public static int argMin(short[] d) {
    return argMin(d, 0, d.length);
  }
  
  public static int argMin(short[] d, int from, int to) {
    Preconditions.checkArgument(from <= to);
    if (from == to) {
      return -1;
    }
    int i = from;
    for (int j = from + 1; j < to; ++j) {
      if (d[j] < d[i]) {
        i = j;
      }
    }
    return i;
  }

  public static int argMin(int[] d) {
    if (d.length == 0) {
      return -1;
    }
    int i = 0;
    for (int j = 1; j < d.length; ++j) {
      if (d[j] < d[i]) {
        i = j;
      }
    }
    return i;
  }

  /**
   * http://tech-algorithm.com/articles/drawing-line-using-bresenham-algorithm
   * 
   * @param x
   * @param y
   * @param x2
   * @param y2
   * @return
   */
  public static int[][] bresenhamLine(int x, int y, int x2, int y2) {
    int w = x2 - x;
    int h = y2 - y;
    int dx1 = 0, dy1 = 0, dx2 = 0, dy2 = 0;
    if (w < 0)
      dx1 = -1;
    else if (w > 0)
      dx1 = 1;
    if (h < 0)
      dy1 = -1;
    else if (h > 0)
      dy1 = 1;
    if (w < 0)
      dx2 = -1;
    else if (w > 0)
      dx2 = 1;
    int longest = Math.abs(w);
    int shortest = Math.abs(h);
    if (!(longest > shortest)) {
      longest = Math.abs(h);
      shortest = Math.abs(w);
      if (h < 0)
        dy2 = -1;
      else if (h > 0)
        dy2 = 1;
      dx2 = 0;
    }
    int numerator = longest >> 1;
    int[][] result = new int[longest + 1][2];
    for (int i = 0; i <= longest; i++) {
      result[i][0] = x;
      result[i][1] = y;
      numerator += shortest;
      if (numerator >= longest) {
        numerator -= longest;
        x += dx1;
        y += dy1;
      } else {
        x += dx2;
        y += dy2;
      }
    }
    return result;
  }

  public static List<IntPair> intermediatePointsOfSegment(IntPair a, IntPair b) {
    int[][] line = bresenhamLine(a.x, a.y, b.x, b.y);
    assert line[0][0] == a.x && line[0][1] == a.y;
    assert line[line.length - 1][0] == b.x && line[line.length - 1][1] == b.y;
    if (line.length == 1) {
      return ImmutableList.of();
    }
    IntPair[] result = new IntPair[line.length - 2];
    for (int i = 1; i < line.length - 1; ++i) {
      result[i - 1] = new IntPair(line[i][0], line[i][1]);
    }
    return Arrays.asList(result);
  }

  /**
   * @return a.length if all array is increasing. Otherwise index i such that
   *         a[i-1] >= a[i].
   */
  public static int firstNonIncreasingIndex(short[] a) {
    int i;
    for (i = Math.min(0, a.length - 1); i < a.length - 1 && a[i] < a[i + 1]; i++) {
    }
    ;
    return i + 1;
  }

  /**
   * @return a.length if all array is increasing. Otherwise index i such that
   *         a[i-1] >= a[i].
   */
  public static int firstNonIncreasingIndex(double[] a) {
    int i;
    for (i = Math.min(0, a.length - 1); i < a.length - 1 && !(a[i] >= a[i + 1]); i++) {
    }
    ;
    return i + 1;
  }

  /**
   * @return a.length if all array is increasing. Otherwise index i such that
   *         a[i-1] <= a[i].
   */
  public static int firstNonDecreasingIndex(short[] a) {
    int i;
    for (i = Math.min(0, a.length - 1); i < a.length - 1 && a[i] > a[i + 1]; i++) {
    }
    ;
    return i + 1;
  }

  public static double median(double[] d) {
    return median(d, 0, d.length);
  }

  public static double median(short[] d) {
    return median(d, 0, d.length);
  }

  public static double median(double[] d, int from, int to) {
    Preconditions.checkArgument(from < to, "from must be less than to");
    double[] a = Arrays.copyOfRange(d, from, to);
    Arrays.sort(a);
    if (a.length % 2 == 0) {
      return (a[a.length / 2 - 1] + a[a.length / 2]) / 2;
    } else {
      return a[a.length / 2];
    }
  }

  public static double median(short[] d, int from, int to) {
    Preconditions.checkArgument(from < to, "from must be less than to");
    short[] a = Arrays.copyOfRange(d, from, to);
    Arrays.sort(a);
    if (a.length % 2 == 0) {
      return (a[a.length / 2 - 1] + a[a.length / 2]) / 2.0;
    } else {
      return a[a.length / 2];
    }
  }

  public static double[] toDoubleArray(short[] data) {
    return toDoubleArray(data, 0, data.length);
  }

  public static double[] toDoubleArray(short[] data, int from, int to) {
    double[] d = new double[to - from];
    for (int i = to; --i >= from;) {
      d[i - from] = data[i];
    }
    return d;
  }

  /**
   * y = a * x + y_0 - a * x_0 The intercept for [i..n-1] is y[i] - slopes[i] *
   * x[i].
   * 
   * @return array of length n - 1.
   */
  public static void slopeOfBestFitLineFromEachPointOnwards(
    double[] x, double[] y, double[] slopes, double[] squaredErrorSum) {
    // Should we first divide x and y by the maximum magnitude to reduce
    // errors?
    int n = x.length;
    Preconditions.checkArgument(y.length == n);
    Preconditions.checkArgument(slopes.length == n - 1);
    Preconditions.checkArgument(squaredErrorSum.length == n - 1);
    // Slope = sum((x_i - x_0) * (y_i - y_0)) / sum((x_i - x_0)^2).
    double sumXiYi = x[n - 1] * y[n - 1], sumXi = x[n - 1], sumYi = y[n - 1], sumXi2 = x[n - 1]
      * x[n - 1], sumYi2 = y[n - 1] * y[n - 1];
    final double smallPositiveValue = 1.5e-6;
    for (int i = n - 1; --i >= 0;) {
      sumXiYi += x[i] * y[i];
      sumXi += x[i];
      sumYi += y[i];
      double xi2 = x[i] * x[i];
      sumXi2 += xi2;
      double yi2 = y[i] * y[i];
      sumYi2 += yi2;
      double numerator = sumXiYi - x[i] * sumYi - y[i] * sumXi + x[i] * y[i] * (n - i);
      double denominator = sumXi2 - 2 * x[i] * sumXi + xi2 * (n - i);
      double a = numerator / denominator;
      slopes[i] = a;
      double value = -a * numerator - 2 * y[i] * sumYi + yi2 * (n - i) + sumYi2;
      if (!Double.isNaN(a)) {
        assert value >= -smallPositiveValue * 1e4 : String.format(
          "i=%d value=%s n=%d x[i:]=%s y[i:]=%s", i, value, n,
          Arrays.toString(Arrays.copyOfRange(x, i, n)),
          Arrays.toString(Arrays.copyOfRange(y, i, n)));
        if (value < 0) {
          logger.info(String.format("value=%s < 0. Probably rounding error.", value));
        }
      }
      squaredErrorSum[i] = Math.abs(value);
    }
  }

  public static void slopeOfBestFitLineFromEachPointOnwards(short[] x, short[] y, double[] slopes) {
    // For some reason, it doesn't work directly with short.
    slopeOfBestFitLineFromEachPointOnwards(
      shortArrayToLongArray(x), shortArrayToLongArray(y), slopes);
  }

  public static void slopeOfBestFitLineFromEachPointOnwards(long[] x, long[] y, double[] slopes) {
    int n = x.length;
    Preconditions.checkArgument(y.length == n);
    Preconditions.checkArgument(slopes.length == n - 1);
    // Slope = sum((x_i - x_0) * (y_i - y_0)) / sum((x_i - x_0)^2).
    long sumXiYi = x[n - 1] * y[n - 1], sumXi = x[n - 1], sumYi = y[n - 1], sumXi2 = x[n - 1]
      * x[n - 1];
    for (int i = n - 1; --i >= 0;) {
      sumXiYi += x[i] * y[i];
      sumXi += x[i];
      sumYi += y[i];
      long xi2 = x[i] * x[i];
      sumXi2 += xi2;
      long numerator = sumXiYi - x[i] * sumYi - y[i] * sumXi + x[i] * y[i] * (n - i);
      long denominator = sumXi2 - 2 * x[i] * sumXi + xi2 * (n - i);
      slopes[i] = fractionToDouble(numerator, denominator);
    }
  }

  public static void slopeOfBestFitLineFromEachPointOnwards(
    short[] xx, short[] yy, double[] slopes, double[] squaredErrorSum, boolean fitSlope) {
    long[] x = shortArrayToLongArray(xx), y = shortArrayToLongArray(yy);
    slopeOfBestFitLineFromEachPointOnwards(x, y, slopes, squaredErrorSum, fitSlope);
  }

  public static void slopeOfBestFitLineFromEachPointOnwards(
    long[] x, long[] y, double[] slopes, double[] squaredErrorSum, boolean fitSlopes) {
    // Should we first divide x and y by the maximum magnitude to reduce
    // errors?
    int n = x.length;
    Preconditions.checkArgument(y.length == n);
    Preconditions.checkArgument(slopes.length == n - 1);
    Preconditions.checkArgument(squaredErrorSum.length == n - 1);
    // Slope = sum((x_i - x_0) * (y_i - y_0)) / sum((x_i - x_0)^2).
    long sumXiYi = x[n - 1] * y[n - 1], sumXi = x[n - 1], sumYi = y[n - 1], sumXi2 = x[n - 1]
      * x[n - 1], sumYi2 = y[n - 1] * y[n - 1];
    for (int i = n - 1; --i >= 0;) {
      sumXiYi += x[i] * y[i];
      sumXi += x[i];
      sumYi += y[i];
      long xi2 = x[i] * x[i];
      sumXi2 += xi2;
      long yi2 = y[i] * y[i];
      sumYi2 += yi2;
      long numerator = sumXiYi - x[i] * sumYi - y[i] * sumXi + x[i] * y[i] * (n - i);
      long denominator = sumXi2 - 2 * x[i] * sumXi + xi2 * (n - i);
      final double value;
      if (fitSlopes) {
        double a = fractionToDouble(numerator, denominator);
        slopes[i] = a;
        value = -2 * y[i] * sumYi + yi2 * (n - i) + sumYi2
          - squareNumeratorAndDivide(numerator, denominator);
        // a^2 den - 2 a num = -a num = - num^2 / den
        if (!Double.isNaN(a)) {
          assert value >= 0 : String.format(
            "i=%d value=%s n=%d x[i:]=%s y[i:]=%s", i, value, n,
            Arrays.toString(Arrays.copyOfRange(x, i, n)),
            Arrays.toString(Arrays.copyOfRange(y, i, n)));
        }
      } else {
        double a = slopes[i];
        value = -2 * y[i] * sumYi + yi2 * (n - i) + sumYi2 + a * (a * denominator - 2 * numerator);
      }
      squaredErrorSum[i] = Math.abs(value);
    }
  }

  public static void squaredErrorSumForLineFromEachPointOnwardsWithFixedSlope(
    long[] x, long[] y, double[] slopes, double[] squaredErrorSum) {

  }

  public static double squareNumeratorAndDivide(long x, long y) {
    if (-3037000499L <= x & x <= 3037000499L) {
      return fractionToDouble(x * x, y);
    } else {
      BigDecimal c = BigDecimal.valueOf(x).pow(2).divide(
        BigDecimal.valueOf(y), 20, RoundingMode.HALF_EVEN);
      return c.doubleValue();
    }
  }

  public static double fractionToDouble(long x, long y) {
    double xAsDouble = (double) x, yAsDouble = (double) y;
    if ((long) xAsDouble == x & (long) yAsDouble == y) {
      return xAsDouble / yAsDouble;
    }
    if (y == 0) {
      return Double.POSITIVE_INFINITY * Long.signum(x);
    }
    BigDecimal xAsBigDecimal = BigDecimal.valueOf(x), yAsBigDecimal = BigDecimal.valueOf(y);
    BigDecimal result = xAsBigDecimal.divide(yAsBigDecimal, 20, RoundingMode.HALF_EVEN);
    return result.doubleValue();
  }

  private static long[] shortArrayToLongArray(short[] x) {
    long[] a = new long[x.length];
    for (int i = x.length; --i >= 0;) {
      a[i] = x[i];
    }
    return a;
  }

  public static int argMax(int[] d) {
    if (d.length == 0) {
      return -1;
    }
    int i = 0;
    for (int j = 1; j < d.length; ++j) {
      if (d[j] > d[i]) {
        i = j;
      }
    }
    return i;
  }

  public static int argMax(short[] d) {
    if (d.length == 0) {
      return -1;
    }
    int i = 0;
    for (int j = 1; j < d.length; ++j) {
      if (d[j] > d[i]) {
        i = j;
      }
    }
    return i;
  }

  public static int findIntervalOfHighestFrequency(List<Range<Double>> ranges, double[] minMax) {
    SortedMap<Double, int[]> sortedMap = new TreeMap<Double, int[]>();
    for (Range<Double> range : ranges) {
      int[] oneZero = new int[] {1, 0};
      int[] minValue = sortedMap.put(range.lowerEndpoint(), oneZero);
      if (minValue != null) {
        oneZero[0] = minValue[0] + 1;
        oneZero[1] = minValue[1];
      }
      int[] zeroOne = new int[] {0, 1};
      int[] maxValue = sortedMap.put(range.upperEndpoint(), zeroOne);
      if (maxValue != null) {
        zeroOne[0] = maxValue[0];
        zeroOne[1] = maxValue[1] + 1;
      }
    }
    int sum = 0;
    for (int[] value : sortedMap.values()) {
      sum += value[0];
      sum += value[1];
    }
    assert sum == ranges.size() * 2;
    List<Map.Entry<Double, int[]>> list = ImmutableList.copyOf(sortedMap.entrySet());
    int[] counts = new int[list.size()];
    int count = 0;
    for (int i = 0; i < counts.length; ++i) {
      count += list.get(i).getValue()[0];
      counts[i] = count;
      count -= list.get(i).getValue()[1];
    }
    int argMax = argMax(counts);
    int i;
    for (i = argMax; --i >= 0;) {
      if (counts[i] != counts[argMax]) {
        break;
      }
    }
    int j;
    for (j = argMax; ++j < counts.length;) {
      if (counts[j] != counts[argMax]) {
        break;
      }
    }
    minMax[0] = list.get(i + 1).getKey();
    minMax[1] = list.get(j - 1).getKey();
    return counts[argMax];
  }

  public static IntArrayList indicesOfTrue(boolean[] potentialPeaks) {
    return indicesOfTrue(potentialPeaks, 0, potentialPeaks.length);
  }

  public static IntArrayList indicesOfTrue(boolean[] potentialPeaks, int from, int to) {
    IntArrayList a = new IntArrayList();
    for (int i = from; i < to; ++i) {
      if (potentialPeaks[i]) {
        a.add(i);
      }
    }
    return a;
  }

  public static int[] toIntArray(boolean[] b) {
    int[] a = new int[b.length];
    for (int i = b.length; --i >= 0;) {
      a[i] = b[i] ? 1 : 0;
    }
    return a;
  }

  public static void removeOrDecrementValueForKey(double key, Double2IntSortedMap sortedMap) {
    int oldValue = sortedMap.get(key);
    Preconditions.checkArgument(oldValue >= 1, "oldValue=%s", oldValue);
    if (oldValue == 1) {
      sortedMap.remove(key);
    } else {
      sortedMap.put(key, oldValue - 1);
    }
  }

  public static void addOrIncrementValueForKey(double key, Double2IntSortedMap sortedMap) {
    int oldValue = sortedMap.get(key);
    sortedMap.put(key, 1 + oldValue);
  }

  public static void addOrRemoveValueForKey(double key, int count, Double2IntSortedMap sortedMap) {
    int oldValue = sortedMap.get(key);
    Preconditions.checkArgument(count >= -oldValue);
    if (count == -oldValue) {
      sortedMap.remove(key);
    } else {
      sortedMap.put(key, oldValue + count);
    }
  }

  public static Double2IntSortedMap frequencyMap(double... a) {
    return frequencyMap(a, 0, a.length);
  }

  public static Double2IntSortedMap frequencyMap(double[] a, int from, int to) {
    Double2IntSortedMap sortedMap = new Double2IntAVLTreeMap();
    addOrIncrementValueForKeys(a, from, to, sortedMap);
    return sortedMap;
  }

  public static void addOrIncrementValueForKeys(
    double[] keys, int from, int to, Double2IntSortedMap sortedMap) {
    for (int i = from; i < to; ++i) {
      addOrIncrementValueForKey(keys[i], sortedMap);
    }
  }

  public static int totalSize(Double2IntSortedMap sortedMap) {
    int sum = 0;
    for (int value : sortedMap.values()) {
      Preconditions.checkArgument(value > 0);
      sum += value;
    }
    return sum;
  }

  public static double median(Double2IntSortedMap sortedMap) {
    ObjectSortedSet<Double2IntMap.Entry> entrySet = sortedMap.double2IntEntrySet();
    int totalSize = totalSize(sortedMap);
    int i = (totalSize - 1) / 2, j = totalSize / 2;
    double x = Double.NaN, y = Double.NaN;
    int sum = 0;
    for (Double2IntMap.Entry entry : entrySet) {
      int sum2 = sum + entry.getIntValue();
      if (sum <= i && sum2 > i) {
        x = entry.getDoubleKey();
      }
      if (sum <= j && sum2 > j) {
        y = entry.getDoubleKey();
      }
      sum = sum2;
    }
    return x / 2 + y / 2;
  }

  public static double medianAbsoluteDeviation(Double2IntSortedMap sortedMap) {
    double median = median(sortedMap);
    Double2IntSortedMap other = new Double2IntAVLTreeMap();
    for (Double2IntMap.Entry entry : sortedMap.double2IntEntrySet()) {
      addOrRemoveValueForKey(Math.abs(entry.getDoubleKey() - median), entry.getIntValue(), other);
    }
    return median(other);
  }

  public static int count(boolean[] potentialPeaks) {
    return count(potentialPeaks, 0, potentialPeaks.length);
  }

  public static int count(boolean[] points, int from, int to) {
    int x = 0;
    for (int i = from; i < to; ++i) {
      if (points[i]) {
        x++;
      }
    }
    return x;
  }

  public static int count(double[] a, double value) {
    int count = 0;
    for (double x : a) {
      if (Double.doubleToLongBits(x) == Double.doubleToLongBits(value)) {
        count++;
      }
    }
    return count;
  }

  public static int count(int[] a, int value) {
    int count = 0;
    for (int x : a) {
      if (x == value) {
        count++;
      }
    }
    return count;
  }

  /**
   * Complexity: a.length * max(log(a.length), windowSize).
   * 
   * @param points
   *          input-output
   */
  public static void keepOnlyLowestInEachWindow(double[] array, int windowSize, boolean[] points) {
    final int n = array.length;
    Preconditions.checkArgument(n == points.length);
    int count = CommonThings.count(points);
    DoubleIntPair[] a = new DoubleIntPair[count];
    int j;
    for (int i = j = 0; i < n; ++i) {
      if (points[i]) {
        a[j++] = new DoubleIntPair(-array[i], i);
      }
    }
    assert j == count;
    // Sort first by -deflection, then by index.
    Arrays.sort(a);
    for (int i = count; --i >= 0;) {
      int index = a[i].y;
      /*
       * Only if index has not been already removed! A removed peak must not
       * have any influence whatsoever. That is, removing it from the very
       * beginning exactly the same result must come out.
       */
      if (points[index]) {
        for (int k = Math.max(0, index - windowSize + 1); k < index; ++k) {
          points[k] = false;
        }
        for (int k = index + 1; k < Math.min(n, index + windowSize); ++k) {
          points[k] = false;
        }
      }
    }
  }

  public static boolean[] toBooleanArray(int[] a, int falseValue) {
    boolean[] b = new boolean[a.length];
    for (int i = a.length; --i >= 0;) {
      b[i] = a[i] != falseValue;
    }
    return b;
  }

  public static double min(double[] a, int from, int to) {
    return a[argMin(a, from, to)];
  }

  public static double min(double[] a) {
    return min(a, 0, a.length);
  }

  public static double max(double[] a, int from, int to) {
    return a[argMax(a, from, to)];
  }

  public static double max(double[] a) {
    return max(a, 0, a.length);
  }

  public static boolean allNonNegative(double[] a) {
    int i;
    for (i = a.length; --i >= 0;) {
      // should handle NaN as well
      if (!(a[i] >= 0)) {
        break;
      }
    }
    return i == -1;
  }

  public static boolean allNonNegative(float[] a) {
    int i;
    for (i = a.length; --i >= 0;) {
      // should handle NaN as well
      if (!(a[i] >= 0)) {
        break;
      }
    }
    return i == -1;
  }

  public static double[] negated(double[] a, int from, int to) {
    double[] b = new double[to - from];
    for (int i = from; i < to; ++i) {
      b[i - from] = -a[i];
    }
    return b;
  }

  public static short[] negated(short[] a, int from, int to) {
    short[] b = new short[to - from];
    for (int i = from; i < to; ++i) {
      b[i - from] = a[i] == Short.MIN_VALUE ? Short.MAX_VALUE : (short) -a[i];
    }
    return b;
  }

  public static double[] nonZeroElements(double[] contourLengths) {
    DoubleArrayList dal = new DoubleArrayList();
    for (double d : contourLengths) {
      if (d != 0) {
        dal.add(d);
      }
    }
    return dal.toDoubleArray();
  }

  public static void open(String filename) throws IOException {
    String osName = System.getProperty("os.name");
    String cmd;
    logger.log(Level.INFO, "Opening: {0}", filename);
    if (osName.contains("Mac OS")) {
      cmd = "open -a /Applications/Firefox.app " + filename;
    } else if (osName.startsWith("Windows")) {
      cmd = "explorer " + filename;
    } else {
      // Not sure ...
      cmd = "firefox " + filename;
    }
    Runtime.getRuntime().exec(cmd);
  }

  public static void appendToFile(String msg, File file) {
    try {
      FileOutputStream fos = new FileOutputStream(file, true);
      fos.write(msg.getBytes("ISO-8859-1"));
      IOUtils.closeQuietly(fos);
    } catch (IOException e) {
    } finally {
    }
  }

  public static void writeToErrFile(Throwable t, Path path) {
    try {
      CommonThings.coreWriteToErrFile(path, t);
    } catch (IOException | RuntimeException e) {
      logger.log(Level.WARNING, e.getMessage(), e);
    }
  }

  private static void coreWriteToErrFile(Path path, Throwable t)
    throws UnsupportedEncodingException, IOException {
    // TODO: It used to be getFullStackTrace, but it disappeared in 3.0.
    String s = "file=" + path + " exception=" + t + " stacktrace="
      + ExceptionUtils.getStackTrace(t) + "\n";
    Files.write(
      Paths.get("errors.log"), s.getBytes("ISO-8859-1"), StandardOpenOption.CREATE,
      StandardOpenOption.APPEND);
  }

  public static byte[] readToByteArrayWithRetryOrNull(
    Path path, long timeToWaitBetweenAttempts, int attempts, Sleeper sleeper) throws InterruptedException {
    Preconditions.checkArgument(attempts >= 1, attempts);
    byte[] fileContent = null;
    int i;
    for (i = 0; i < attempts - 1; ++i) {
      try {
        fileContent = Files.readAllBytes(path);
      } catch (IOException e) {
      }
      if (fileContent == null || fileContent.length == 0) {
        logger.log(Level.INFO, "Waiting a bit more to read {0}.", path);
        sleeper.sleep(timeToWaitBetweenAttempts);
      } else {
        break;
      }
    }
    if (i == attempts) {
      logger.log(Level.WARNING, "Exceeded {0} attempts.", attempts);
    }
    if (fileContent == null || fileContent.length == 0) {
      try {
        fileContent = Files.readAllBytes(path);
      } catch (IOException e2) {
        logger.log(Level.WARNING, "Could not read file {0} because: {1}", new Object[] {path, e2});
      }
    }
    return fileContent;
  }

  public static void openQuietly(String s) {
    try {
      open(s);
    } catch (IOException e) {
      logger.log(Level.WARNING, e.getMessage(), e);
    }
  }

  public static int argMinAbsDifference(double[] a, double x) {
    int argMin = 0;
    double diff = Math.abs(a[0] - x);
    for (int i = 1; i < a.length; ++i) {
      double currentDiff = Math.abs(a[i] - x);
      if (currentDiff < diff) {
        argMin = i;
        diff = currentDiff;
      }
    }
    return argMin;
  }

  public static void printStartAndEndOfArray(short[] a, int m, String name) {
    System.out.println(name + "[0:" + m + "]=" + Arrays.toString(Arrays.copyOf(a, m)));
    System.out.println(name + "[-" + m + ":]="
      + Arrays.toString(Arrays.copyOfRange(a, a.length - m, a.length)));
  }

  public static void printStartAndEndOfArray(double[] a, int m, String name) {
    System.out.println(name + "[0:" + m + "]=" + Arrays.toString(Arrays.copyOf(a, m)));
    System.out.println(name + "[-" + m + ":]="
      + Arrays.toString(Arrays.copyOfRange(a, a.length - m, a.length)));
  }

  public static boolean allSelectedAreNonPositive(double[] a, boolean[] indicator) {
    Preconditions.checkArgument(a.length == indicator.length);
    int i;
    for (i = indicator.length; --i >= 0;) {
      if (indicator[i] && !(a[i] <= 0)) {
        break;
      }
    }
    return i == -1;
  }

  public static DoubleArrayList selected(double[] a, boolean[] indicator) {
    int n = count(indicator);
    DoubleArrayList result = new DoubleArrayList(n);
    for (int i = 0; i < indicator.length; ++i) {
      if (indicator[i]) {
        result.add(a[i]);
      }
    }
    return result;
  }

  public static IntArrayList selected(int[] a, boolean[] indicator) {
    int n = count(indicator);
    IntArrayList result = new IntArrayList(n);
    for (int i = 0; i < indicator.length; ++i) {
      if (indicator[i]) {
        result.add(a[i]);
      }
    }
    return result;
  }

  public static Rectangle2D boundsOfUnion(Iterable<Shape> shapes) {
    Iterator<Shape> it = shapes.iterator();
    Rectangle2D bounds = it.next().getBounds2D();
    while (it.hasNext()) {
      Shape shape = it.next();
      Rectangle2D.union(bounds, shape.getBounds2D(), bounds);
    }
    return bounds;
  }

  public static long sum(int[] a) {
    long sum = 0;
    for (int x : a) {
      sum += x;
    }
    return sum;
  }

  public static long sum(short[] a) {
    long sum = 0;
    for (short x : a) {
      sum += x;
    }
    return sum;
  }

  public static short[] lastFractionPiece(short[] a, double fraction) {
    Preconditions.checkArgument(0 <= fraction & fraction <= 1);
    return Arrays.copyOfRange(a, (int) Math.floor(a.length * (1 - fraction)), a.length);
  }

  public static int countAtEnd(short[] z, int value) {
    int i = z.length;
    while (--i >= 0) {
      if (z[i] != value) {
        break;
      }
    }
    return z.length - 1 - i;
  }

  public static double sum(double[] time) {
    return sum(time, 0, time.length);
  }

  public static double sum(double[] time, int from, int to) {
    double sum = 0;
    for (int i = from; i < to; ++i) {
      sum += time[i];
    }
    return sum;
  }

  public static boolean increasing(double[] sortedSlopes) {
    for (int i = 0; i < sortedSlopes.length - 1; ++i) {
      if (!(sortedSlopes[i] < sortedSlopes[i + 1])) {
        return false;
      }
    }
    return true;
  }

  public static boolean increasing(int[] a) {
    for (int i = 0; i < a.length - 1; ++i) {
      if (!(a[i] < a[i + 1])) {
        return false;
      }
    }
    return true;
  }

  public static boolean increasing(short[] a) {
    for (int i = 0; i < a.length - 1; ++i) {
      if (!(a[i] < a[i + 1])) {
        return false;
      }
    }
    return true;
  }

  public static boolean nonDecreasing(short[] a) {
    for (int i = 0; i < a.length - 1; ++i) {
      if (!(a[i] <= a[i + 1])) {
        return false;
      }
    }
    return true;
  }

  public static boolean increasing(IntList a) {
    IntListIterator it = a.iterator();
    if (!it.hasNext()) {
      return true;
    }
    int x = it.nextInt();
    while (it.hasNext()) {
      int y = it.nextInt();
      if (!(x < y)) {
        return false;
      }
      x = y;
    }
    return true;
  }

  public static int indexOfNearestHalfEvenInSortedArray(double d, double[] sortedSlopes) {
    int bs = Arrays.binarySearch(sortedSlopes, d);
    if (bs >= 0) {
      return bs;
    } else {
      int insertionPoint = -bs - 1;
      if (insertionPoint == sortedSlopes.length) {
        return sortedSlopes.length - 1;
      }
      assert sortedSlopes[insertionPoint] > d;
      if (insertionPoint == 0
        || Math.abs(d - sortedSlopes[insertionPoint - 1]) > Math.abs(d
          - sortedSlopes[insertionPoint])
        || (Math.abs(d - sortedSlopes[insertionPoint - 1]) == Math.abs(d
          - sortedSlopes[insertionPoint]) && (insertionPoint & 1) == 0)) {
        return insertionPoint;
      } else {
        return insertionPoint - 1;
      }
    }
  }

  public static int argMinNotNaNFirst(double[] a) {
    int i = 0;
    while (i < a.length && Double.isNaN(a[i])) {
      i++;
    }
    if (i == a.length) {
      return -1;
    }
    int argMin = i;
    double min = a[i];
    assert !Double.isNaN(min);
    for (int j = i + 1; j < a.length; ++j) {
      if (!Double.isNaN(a[j]) && a[j] < min) {
        min = a[argMin = j];
      }
    }
    return argMin;
  }

  public static int middleIndexOf(double[] absError, double d) {
    int c = count(absError, d);
    int result = -1;
    int j = 0;
    for (int i = 0; i < absError.length; ++i) {
      if (absError[i] == d) {
        if (j == (c - 1) / 2) {
          result = i;
          break;
        }
        j++;
      }
    }
    assert (result == -1) == (c == 0);
    return result;
  }

  public static <T extends Collection<?>> List<T> filterForSizeAtLeast(
    List<T> preliminaryPaths, int minimumSize) {
    List<T> result = new ArrayList<>();
    for (T t : preliminaryPaths) {
      if (t.size() >= minimumSize) {
        result.add(t);
      }
    }
    return result;
  }

  public static class MinMaxXys {
    public MinMaxXys(int xForMinS, int yForMinS, int minS, int xForMaxS, int yForMaxS, int maxS) {
      this.xForMinS = xForMinS;
      this.yForMinS = yForMinS;
      this.minS = minS;
      this.xForMaxS = xForMaxS;
      this.yForMaxS = yForMaxS;
      this.maxS = maxS;
    }

    public int xForMinS, yForMinS, minS, xForMaxS, yForMaxS, maxS;

    @Override
    public String toString() {
      return String.format(
        "min:(x=%d, y=%d, s=%d) max:(x=%d, y=%d, s=%d)", xForMinS, yForMinS, minS, xForMaxS,
        yForMaxS, maxS);
    }
  }

  public static MinMaxXys minMaxXys(short[][] heights) {
    int minS = Integer.MAX_VALUE, maxS = Integer.MIN_VALUE, xForMinS = -1, yForMinS = -1, xForMaxS = -1, yForMaxS = -1;
    for (int i = 0; i < heights.length; ++i) {
      for (int j = 0; j < heights[i].length; ++j) {
        int s = heights[i][j];
        assert Short.MIN_VALUE <= s & s <= Short.MAX_VALUE;
        if (minS > s) {
          minS = s;
          xForMinS = i;
          yForMinS = j;
        }
        if (maxS < s) {
          maxS = s;
          xForMaxS = i;
          yForMaxS = j;
        }
      }
    }
    return new MinMaxXys(xForMinS, yForMinS, minS, xForMaxS, yForMaxS, maxS);
  }

  public static <T> int countDifferentFrom(List<T> cc, T v) {
    int c = 0;
    for (T t : cc) {
      if (!Objects.equal(t, v)) {
        ++c;
      }
    }
    return c;
  }

  public static int countDifferentFrom(double[] cc, double v) {
    int c = 0;
    for (int i = cc.length; --i >= 0;) {
      if (cc[i] != v) {
        ++c;
      }
    }
    return c;
  }

  public static int countDifferentFrom(float[] cc, float v) {
    int c = 0;
    for (int i = cc.length; --i >= 0;) {
      if (cc[i] != v) {
        ++c;
      }
    }
    return c;
  }

  public static short min(ShortList z) {
    Preconditions.checkArgument(!z.isEmpty());
    short min = Short.MAX_VALUE;
    for (ShortListIterator it = z.iterator(); it.hasNext(); ) {
      min = CommonThings.min(min, it.nextShort());
    }
    return min;
  }

  public static short max(ShortList z) {
    Preconditions.checkArgument(!z.isEmpty());
    short max = Short.MIN_VALUE;
    for (ShortListIterator it = z.iterator(); it.hasNext(); ) {
      max = CommonThings.max(max, it.nextShort());
    }
    return max;
  }

  public static int min(int[] iArray) {
    Preconditions.checkArgument(iArray.length != 0);
    int min = Integer.MAX_VALUE;
    for (int i = iArray.length; --i >= 0;) {
      min = Math.min(min, iArray[i]);
    }
    return min;
  }

  public static int max(int[] iArray) {
    Preconditions.checkArgument(iArray.length != 0);
    int max = Integer.MIN_VALUE;
    for (int i = iArray.length; --i >= 0;) {
      max = Math.max(max, iArray[i]);
    }
    return max;
  }

  public static float max(float[] fArray) {
    Preconditions.checkArgument(fArray.length != 0);
    float max = Float.NEGATIVE_INFINITY;
    for (int i = fArray.length; --i >= 0;) {
      max = Math.max(max, fArray[i]);
    }
    return max;
  }

  public static float min(float[] fArray) {
    Preconditions.checkArgument(fArray.length != 0);
    float min = Float.POSITIVE_INFINITY;
    for (int i = fArray.length; --i >= 0;) {
      min = Math.min(min, fArray[i]);
    }
    return min;
  }

  public static int[] normal(int vertices) {
    int[] a = new int[vertices];
    for (int i = a.length; --i >= 0;) {
      a[i] = i;
    }
    return a;
  }

  public static int[] shuffledIndices(int vertices, Random rnd) {
    int[] a = normal(vertices);
    Collections.shuffle(Arrays.asList(a), rnd);
    return a;
  }

  public static int countLessThan(int[] a, int x) {
    int count = 0;
    for (int i = a.length; --i >= 0;) {
      if (a[i] < x) {
        ++count;
      }
    }
    return count;
  }

  public static int countGreaterThan(int[] a, int x) {
    int count = 0;
    for (int i = a.length; --i >= 0;) {
      if (a[i] > x) {
        ++count;
      }
    }
    return count;
  }

  public static int countDifferentFrom(int[] a, int x) {
    int count = 0;
    for (int i = a.length; --i >= 0;) {
      if (a[i] != x) {
        ++count;
      }
    }
    return count;
  }

  public static int countDifferentFrom(byte[] a, byte x) {
    int count = 0;
    for (int i = a.length; --i >= 0;) {
      if (a[i] != x) {
        ++count;
      }
    }
    return count;
  }

  public static IntArrayList[] nCopiesArray(int n, IntArrayList x) {
    IntArrayList[] a = new IntArrayList[n];
    Arrays.fill(a, x);
    return a;
  }

  public static FloatArrayList[] nCopiesArray(int n, FloatArrayList x) {
    FloatArrayList[] a = new FloatArrayList[n];
    Arrays.fill(a, x);
    return a;
  }

  @SuppressWarnings("unchecked")
  public static Collection<File> toFileCollection(Collection<?> c) {
    return (Collection<File>) c;
  }

  public static boolean includes(boolean[] a, boolean[] b) {
    int n = a.length;
    Preconditions.checkArgument(n == b.length);
    for (int i = 0; i < n; ++i) {
      if (b[i] & !a[i]) {
        return false;
      }
    }
    return true;
  }

  public static boolean includesNot(boolean[] a, boolean[] b) {
    int n = a.length;
    Preconditions.checkArgument(n == b.length);
    for (int i = 0; i < n; ++i) {
      if (!(a[i] | b[i])) {
        return false;
      }
    }
    return true;
  }

  public static int countLessThan(double[] a, int x) {
    int count = 0;
    for (int i = 0; i < a.length; ++i) {
      if (a[i] < 0) {
        ++count;
      }
    }
    return count;
  }

  public static <T> List<T> selectedNot(List<T> a, boolean[] ignore) {
    Preconditions.checkArgument(a.size() == ignore.length);
    List<T> result = new ArrayList<>();
    for (int i = 0; i < ignore.length; ++i) {
      if (!ignore[i]) {
        result.add(a.get(i));
      }
    }
    return result;
  }

  public static void reverse(int[] a, int from, int to) {
    int i = from - 1, j = to;
    while (++i < --j) {
      int x = a[i];
      a[i] = a[j];
      a[j] = x;
    }
  }

  public static void reverse(double[] a, int from, int to) {
    int i = from - 1, j = to;
    while (++i < --j) {
      double x = a[i];
      a[i] = a[j];
      a[j] = x;
    }
  }

  public static void reverse(short[] a, int from, int to) {
    int i = from - 1, j = to;
    while (++i < --j) {
      short x = a[i];
      a[i] = a[j];
      a[j] = x;
    }
  }

  public static IntList sorted(IntList headsWithChangedTail) {
    int[] a = headsWithChangedTail.toIntArray();
    Arrays.sort(a);
    return IntArrayList.wrap(a);
  }

  public static double stddev(double[] a, int from, int to) {
    Preconditions.checkPositionIndexes(from, to, a.length);
    return Math.sqrt(StatUtils.variance(a, from, to - from));
  }

  public static DoublePair meanAndStddev(double[] a, int from, int to) {
    Preconditions.checkPositionIndexes(from, to, a.length);
    double mean = mean(a, from, to);
    return DoublePair.of(mean, Math.sqrt(StatUtils.variance(a, mean, from, to - from)));
  }

  public static DoublePair meanAndStddevIgnoringNaN(double[] a, int from, int to) {
    int nans = 0;
    for (int i = from; i < to; ++i) {
      if (Double.isNaN(a[i])) {
        ++nans;
      }
    }
    double[] b;
    if (nans == 0) {
      return meanAndStddev(a, from, to);
    } else {
      b = new double[to - from - nans];
      int j = 0;
      for (int i = from; i < to; ++i) {
        if (!Double.isNaN(a[i])) {
          b[j++] = a[i];
        }
      }
      assert j == b.length;
      return meanAndStddev(b, 0, b.length);
    }
  }

  public static double stddev(double[] a) {
    return stddev(a, 0, a.length);
  }

  public static int totalSize(IntCollection[] a) {
    int s = 0;
    for (IntCollection c : a) {
      s += c.size();
    }
    return s;
  }

  public static int lastArgMin(double[] d, int from, int to) {
    Preconditions.checkArgument(from <= to);
    if (from == to) {
      return -1;
    }
    int i = to - 1;
    for (int j = i - 1; j >= from; --j) {
      if (d[j] < d[i]) {
        i = j;
      }
    }
    return i;
  }

  public static DoubleList toDoubleList(IntList peakIndices) {
    double[] d = new double[peakIndices.size()];
    for (int i = d.length; --i >= 0;) {
      d[i] = peakIndices.getInt(i);
    }
    return DoubleArrayList.wrap(d);
  }

  public static <K, V, T extends List<V>> Map<K, List<V>> unionMapsOfLists(Iterable<Map<K, T>> maps) {
    Map<K, List<V>> result = Maps.newHashMap();
    for (Map<K, ? extends List<V>> map : maps) {
      result = unionTwoMapsOfLists(result, map);
    }
    return result;
  }

  @SafeVarargs
  public static <K, V, T extends List<V>> Map<K, List<V>> unionMapsOfLists(Map<K, T>... maps) {
    return unionMapsOfLists(Arrays.asList(maps));
  }

  private static <K, V> Map<K, List<V>> unionTwoMapsOfLists(
    Map<K, ? extends List<V>> fetchShapes, Map<K, ? extends List<V>> otherShapes) {
    Map<K, List<V>> result = Maps.newHashMap();
    for (Map.Entry<K, ? extends List<V>> e : fetchShapes.entrySet()) {
      result.put(e.getKey(), Lists.newArrayList(e.getValue()));
    }
    for (Map.Entry<K, ? extends List<V>> e : otherShapes.entrySet()) {
      List<V> list = result.get(e.getKey());
      if (list == null) {
        list = new ArrayList<>();
        result.put(e.getKey(), list);
      }
      list.addAll(e.getValue());
    }
    return Collections.unmodifiableMap(result);
  }

  public static short min(short[] z, int from, int to) {
    return z[argMin(z, from, to)];
  }

  public static short min(short[] z) {
    return min(z, 0, z.length);
  }

  public static short max(short[] z) {
    return z[argMax(z, 0, z.length)];
  }

  public static double mean(short[] x, int from, int to) {
    double xAvg = 0;
    double len = (double) (to - from);
    for (int i = from; i < to; ++i) {
      xAvg += x[i] / len;
    }
    return xAvg;
  }

  public static double[] nCopies(int length, double d) {
    double[] a = new double[length];
    Arrays.fill(a, d);
    return a;
  }

  public static <T> int findContiguousSegmentLengthAtStart(
    Iterable<? extends T> iterable, Predicate<? super T> predicate) {
    int len = 0;
    for (T t : iterable) {
      if (predicate.apply(t)) {
        ++len;
      } else {
        break;
      }
    }
    return len;
  }

  public static double min(double s, double t) {
    return s < t ? s : t;
  }

  public static short min(short s, short t) {
    return s < t ? s : t;
  }

  public static short max(short s, short t) {
    return s < t ? t : s;
  }

  public static long sum(IntCollection values) {
    return sum(values.toIntArray());
  }

  public static boolean[] nonEqual(int[] a, int x) {
    boolean[] b = new boolean[a.length];
    for (int i = a.length; --i >= 0;) {
      b[i] = a[i] != x;
    }
    return b;
  }

  public static short[] concat(short[] a, short[] b) {
    short[] c = Arrays.copyOf(a, a.length + b.length);
    System.arraycopy(b, 0, c, a.length, b.length);
    return c;
  }

  public static double[] concat(double[] a, double[] b) {
    double[] c = Arrays.copyOf(a, a.length + b.length);
    System.arraycopy(b, 0, c, a.length, b.length);
    return c;
  }

  public static void createDirectoryPathIfNeeded(Path targetDir) {
    try {
      Files.createDirectories(targetDir);
    } catch (IOException e) {
      throw new MyRuntimeException(e.getMessage(), e);
    }
  }

  public static Path createDirIfNeeded(String dir) {
    Path cpsDirectory = dir.isEmpty() ? null : Paths.get(dir);
    if (cpsDirectory != null) {
      createDirectoryPathIfNeeded(cpsDirectory);
    }
    return cpsDirectory;
  }

  /**
   * @param d
   * @param threshold
   * @return d.length if no element is found
   */
  public static int indexOfFirstElementGreaterThanOrEqualTo(double[] d, double threshold) {
    int i;
    for (i = 0; i < d.length; ++i) {
      if (d[i] >= threshold) {
        break;
      }
    }
    return i;
  }

  public static int indexOfFirstElementLessThanOrEqualTo(double[] d, double threshold) {
    int i;
    for (i = 0; i < d.length; ++i) {
      if (d[i] <= threshold) {
        break;
      }
    }
    return i;
  }

  public static double[] multiply(double[] a, double d) {
    double[] b = new double[a.length];
    for (int i = a.length; --i >= 0;) {
      b[i] = a[i] * d;
    }
    return b;
  }

  public static double[] multiply(short[] a, double d) {
    double[] b = new double[a.length];
    for (int i = a.length; --i >= 0;) {
      b[i] = a[i] * d;
    }
    return b;
  }

  /**
   * new File(captureDir).list()
   */
  public static Path[] listDir(Path captureDir) {
    try (DirectoryStream<Path> stream = Files.newDirectoryStream(captureDir)) {
      return Iterables.toArray(stream, Path.class);
    } catch (IOException e) {
      logger.log(Level.WARNING, e.getMessage(), e);
      return null;
    }
  }

  public static Path[] listDirOrNull(Path captureDir, String syntaxAndPattern) {
    final PathMatcher pathMatcher = captureDir.getFileSystem().getPathMatcher(syntaxAndPattern);
    Filter<Path> filter = new Filter<Path>() {
      @Override
      public boolean accept(Path entry) throws IOException {
        return pathMatcher.matches(entry);
      }
    };
    try (DirectoryStream<Path> stream = Files.newDirectoryStream(captureDir, filter)) {
      return Iterables.toArray(stream, Path.class);
    } catch (IOException e) {
      logger.log(Level.WARNING, e.getMessage(), e);
      return null;
    }
  }

  public static double[] parseDoubles(String[] a) {
    double[] d = new double[a.length];
    for (int i = a.length; --i >= 0;) {
      d[i] = Double.parseDouble(a[i]);
    }
    return d;
  }

  public static boolean isNaNOrFiniteNonNegative(double x) {
    return Double.isNaN(x) | (x >= 0 & x != Double.POSITIVE_INFINITY);
  }

  public static short[] reversed(short[] z, int from, int to) {
    short[] copy = Arrays.copyOfRange(z, from, to);
    reverse(copy, 0, copy.length);
    return copy;
  }

  public static String toString(short[] a, int from, int to) {
    return Arrays.toString(Arrays.copyOfRange(a, from, to));
  }

  public static String[] parseArrayRepr(String s, String name) {
    Preconditions.checkArgument(s.startsWith("[") & s.endsWith("]"));
    String s1 = s.substring(1, s.length() - 1);
    String[] s2 = StringUtils.splitByWholeSeparator(s1, ", " + name);
    return s2;
  }

  public static short[] merge(short[] a, short[] b) {
    Preconditions.checkArgument(nonDecreasing(a));
    Preconditions.checkArgument(nonDecreasing(b));
    short[] result = new short[a.length + b.length];
    int i, j, k;
    for (i = j = k = 0; i != a.length & j != b.length; ++k) {
      if (a[i] < b[j]) {
        result[k] = a[i++];
      } else {
        result[k] = b[j++];
      }
    }
    System.arraycopy(a, i, result, k, a.length - i);
    k += a.length - i;
    System.arraycopy(b, j, result, k, b.length - j);
    k += b.length - j;
    return result;
  }

  public static int uniq(short[] a) {
    int i = 0;
    for (int j = 0; j < a.length; ++j) {
      if (j == 0 || a[j] != a[j - 1]) {
        a[i++] = a[j];
      }
    }
    return i;
  }

  public static double squareSum(double[] diff) {
    double sum = 0;
    for (int i = 0; i < diff.length; ++i) {
      sum += diff[i] * diff[i];
    }
    return sum;
  }

  public static void reverse(short[] a) {
    reverse(a, 0, a.length);
  }

  public static boolean any(byte[] pad) {
    boolean result = false;
    for (int i = 0; i < pad.length & !result; ++i) {
      result |= pad[i] != 0;
    }
    return result;
  }

  public static boolean any(short[] pad) {
    return any(pad, 0, pad.length);
  }
  
  public static boolean any(short[] pad, int from, int to) {
    boolean result = false;
    for (int i = from; i < to & !result; ++i) {
      result |= pad[i] != 0;
    }
    return result;
  }

  public static String replaceLastOccurenceOrFail(
    String searchable, String toRemove, String replacement) {
    int index = searchable.lastIndexOf(toRemove);
    Preconditions.checkArgument(index != -1, "%s does not contain %s", searchable, toRemove);
    StringBuilder sb = new StringBuilder(searchable.length() - toRemove.length()
      + replacement.length());
    sb.append(searchable.substring(0, index));
    sb.append(replacement);
    sb.append(searchable.substring(index + toRemove.length()));
    return sb.toString();
  }

  public static int sum(boolean[] a, int from, int to) {
    int x = 0;
    for (int i = from; i < to; ++i) {
      if (a[i]) {
        ++x;
      }
    }
    return x;
  }
  
  public static final Executor callerRunsExecutor = new Executor() {
    @Override
    public void execute(Runnable command) {
      command.run();
    }
  };

  public static <T> List<T> slice(List<T> a, int from, int to, int step) {
    List<T> b = new ArrayList<>();
    ListIterator<T> li = a.listIterator(from);
    while (li.hasNext()) {
      b.add(li.next());
      for (int i = 0; i < step - 1 & li.hasNext(); ++i) {
        li.next();
      }
    }
    return b;
  }

  public static <T> T only(Iterable<? extends T> a) {
    Iterator<? extends T> it = a.iterator();
    Preconditions.checkArgument(it.hasNext(), "empty");
    T t = it.next();
    Preconditions.checkArgument(!it.hasNext(), "more than one element");
    return t;
  }

  public static void sleep(long millis, Sleeper sleeper) {
    try {
      sleeper.sleep(millis);
    } catch (InterruptedException e) {
      throw new MyRuntimeException("Interrupted while sleeping.", e);
    }
  }

  public static void squareInPlace(double[] minR2) {
    for (int i = minR2.length; --i >= 0; ) {
      minR2[i] *= minR2[i];
    }
  }

  public static void sleepS(double timeS, Sleeper sleeper) {
    sleep((long) Math.round(timeS * 1000), sleeper);
  }

  public static double[] repeat(int iterations, double[] a) {
    double[] b = Arrays.copyOf(a, a.length * iterations);
    for (int i = 1; i < iterations; ++i) {
      System.arraycopy(a, 0, b, i * a.length, a.length);
    }
    return b;
  }

  // /**
  // * Adapted from
  // * http://www.johndcook.com/blog/2008/10/20/comparing-two-ways-to
  // * -fit-a-line-to-data/. Assumes x goes from 0 to y.length - 1.
  // */
  // public static LinearFunction fitLine(short[] y) {
  // long sy = 0;
  // int n = y.length;
  // for (int i = 0; i < n; ++i) {
  // sy += y[i];
  // }
  // double stt = 0.0, sts = 0.0;
  // for (int i = 0; i < n; ++i) {
  // double t = i - (n - 1) / 2.0;
  // stt += t * t;
  // sts += t * y[i];
  // }
  // assert (sts == 0) || (n > 1);
  // // sts could also be zero because of rounding errors
  // if (stt == 0) {
  // return null;
  // }
  // double slope = sts / stt;
  // long sx = (n - 1) * n / 2;
  // double intercept = (sy - sx * slope) / n;
  // return new LinearFunction(slope, intercept);
  // }
}
